/**
 * 对单链表进行简单选择排序
 * 选择排序：每次选择一个最小的元素，放到头位置
 */
#include"../linear/LinkedList.h"

/**
 * 这里假设没有头节点
 * 用
 */
void selectSort(LinkedList* L){
    LinkedListNode *temp=L;//temp表示当前已经要被替换的节点
    //cur是工作指针（查找最大值），工作指针的前驱，最大指针的前驱，最大指针（记录最大值）
    LinkedListNode *cur,*cur_pre,*max_pre,*max_cur;
    L=nullptr;
    while (temp!=nullptr)
    {
        //当前工作指针和最大值都设置为当前值
        cur=max_cur=temp;cur_pre=max_pre=nullptr;
        while (cur!=nullptr)
        {
            //如果当前的比记录的最大值大，那么就
            if(cur->val>max_cur->val){
                max_cur=cur;
                max_pre=cur_pre;
            }
            //查找下一个
            cur_pre=cur;
            cur=cur->next;
        }//退出while之后，max_cur保存的就是最大的节点，现在要插入到头节点
        if(max_cur==temp){//如果最大节点就是头节点，直接让temp移动一位
            temp=temp->next;
        }else{//如果不是头节点，那么就让
            max_pre->next=max_cur->next;
        }
        //这里使用的是选择最大值，连接到头（没有头），将L重新设置位当前的头，然后不断后移的方法
        max_cur->next=L;
        L=max_cur;
        
    }
    

}
